package two;

import java.util.Scanner;

public class test11086 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i]=scanner.nextInt();
        }
        InsertSort(array,n);
        System.out.print("Insert sort:");
        for (int i = 0; i < n; i++) {
            System.out.print(" "+array[i]);
        }

        for (int i = 0; i < n; i++) {
            array[i]=scanner.nextInt();
        }
        System.out.print("\nNatural merge sort:");
        InsertSort(array,n);
        for (int i = 0; i < n; i++) {
            System.out.print(" "+array[i]);
        }

        for (int i = 0; i < n; i++) {
            array[i]=scanner.nextInt();
        }
        System.out.print("\nQuick sort:");
        InsertSort(array,n);
        for (int i = 0; i < n; i++) {
            System.out.print(" "+array[i]);
        }
    }

    private static void InsertSort(int[] array, int n) {
        int i,j,k;
        for(i = 1;i<n;i++){
            for(j= i-1;j>=0;j--){
                if(array[i]>array[j])
                    break;
            }
            if(i-1!=j) {
                int temp = array[i];
                for (k = i - 1; k > j; k--) {
                    array[k + 1] = array[k];
                }
                array[k + 1] = temp;
            }
        }
    }
}
